package 链式结构.linkedlist;

import org.w3c.dom.Node;
import 链式结构.List;

/**
 * @ClassName: LinkedList
 * @Description: 链表
 * @author: wangz48
 * @date: 2021-12-27 9:57
 */

public class LinkedList<E> implements List {

    /*==============成员变量================*/
    /**
     * 链表长度
     */
    private int size;
    /**
     * 头结点
     */
    private Node first;



    /*===============构造方法===============*/
    /**
     * 默认无参构造，因为不需要传容量
     */
    public LinkedList(){
    }


    /*===============成员方法===============*/

    /**
     * 清空链表
     * size = 0;
     * first = null
     */
    @Override
    public void clear() {
        size = 0;
        first = null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object element) {
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(Object element) {
        add(size,element);
    }

    @Override
    public Object get(int index) {
        Node<E> node = node(index);
        return node.element;
    }

    @Override
    public Object set(int index, Object element) {
        Node<E> node = node(index);
        E old = node.element;;
        node.element = (E) element;
        return old;
    }

    /**
     * 添加元素。需要找index-1的元素
     * @param index
     * @param element
     */
    @Override
    public void add(int index, Object element) {
        if (index == 0){
            first = new Node<>(element, first);
        }else {
            //前一个节点
            Node<E> preNode = node(index - 1);
            //新节点
            Node<E> node = (Node<E>) new Node(element, preNode.next);
            //前一个节点指向新的
            preNode.next = node;
        }
        //长度增加
        size++;
    }
    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 获取前面的元素，用next指向index+1的节点
     * @param index
     * @return
     */
    @Override
    public Object remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0){
         first = first.next;
        }else {
            Node<E> prevNode = node(index - 1);
            prevNode.next = prevNode.next.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(Object element) {
        if (element == null){
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null){return i;}
                node = node.next;
            }
        }else {
            Node<E> node = first;
            for (int i = 0; i < size; i++){
                if (element.equals(node.element)){return i;}
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("size=").append(size).append(",[");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if(i != 0){
                stringBuilder.append(",");
            }
            stringBuilder.append(node.element);
            node = node.next;
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    /*===============其他方法===============*/

    /**
     *  边界检查
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index"+index+",Size:"+size);
    }
    /**
     * 权限检查
     */
    private void rangeCheck(int index){
        if (index < 0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * add检查索引越界
     */
    private void rangeCheckForAdd(int index){
        if (index < 0 || index > size){
            outOfBounds(index);
        }
    }


    /*===============节点内部类===============*/

    /**
     * 节点类
     */
    private static class Node<E>{
        /**
         * 存储的元素
         */
        E element;

        /**
         * 下一个节点
         */
        Node<E> next;

        /**
         * 构造函数
         */
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

}
